/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-02-01
 * Time: 21:11
 */

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

class Solution {
//     思路一:
//     用线性表存储 所有的节点
//     然后利用下标进行重排
//     思路二:
//     寻找链表中间节点 + 链表反转 + 链表合并
    public void reorderList(ListNode head) {
        // 找到链表中点
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        // 链表反转
        ListNode cur=slow;
        ListNode prev=null;
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=prev;
            prev=cur;
            cur=next;
        }
        // 合并链表
        ListNode tail=prev;
        ListNode newHead=head;
        // 记录下一个节点
        ListNode ln=newHead.next;
        ListNode rn=tail.next;
        while(ln!=null&&rn!=null){
            // 连接之后 指针后移
            newHead.next=tail;
            newHead=ln;
            tail.next=newHead;
            tail=rn;
            ln=ln.next;
            rn=rn.next;
        }
    }
}
